package com.chj.leetcode.tijie300to350;

public class Code300_LongestIncreasingSubsequence {
	public static int getdp2(int[] arr) {
		int[] ends = new int[arr.length];
		ends[0] = arr[0];

		int rightEnd = 0;
		int ll = 0;
		int rr = 0;

		int ans = 1;
		for (int i = 1; i < arr.length; i++) {
			ll = 0;
			rr = rightEnd;
			ll = left_bound(ends, arr[i], ll, rr);

			rightEnd = Math.max(rightEnd, ll);
			ends[ll] = arr[i];
			ans = Math.max(ans, ll + 1);
		}
		return ans;
	}

	public static int left_bound(int[] nums, int target, int l, int r) {
		int left = l, right = r;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) {
				left = mid + 1;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else if (nums[mid] == target) {
				// 别返回，锁定左侧边界
				right = mid - 1;
			}
		}
		// 最后要检查 left 越界的情况
//		if (left >= nums.length || nums[left] != target)
//			return -1;
		return left;
	}

}
